Fullstack-Study

자료구조

1. 배열(Array)

1-1. 정적 배열 (static Array)

고정된 크기 배열 , 메모리 연속 할당
데이터 저장 원리 : 연속된 메모리 공간에 인덱스 순서대로 저장
데이터 조회 원리 : 인덱스로 바로 접근 -> O(1)
데이터 삽입/삭제 원리 :
- 삽입 : 중간에 넣으려면 뒤쪽 데이터 이동 -> O(n)
- 삭제 : 삭제 후 뒤쪽 데이터 이동 -> O(n)
사용 이유 / 사용 시점
- 고정 크기, 빠른 조회 필요 시 사용
- 예 : 달력, 월별 통계, 이미지 픽셀

int[] arr = new int[5];
arr[0] = 10;

1-2. 동적 배열 (ArrayList)

필요시 크기 자동 확장
데이터 저장 원리 : 공간 부족 시 새 배열 생성 후 기존 데이터 복사
데이터 조회 원리 : 인덱스 접근 -> O(1)
데이터 삽입/삭제 원리
- 끝에 추가 : O(1) 평균
- 중간 삽입/삭제 : O(n) (뒤 요소 이동)
사용 이유 / 사용 시점
- 크기 변동 데이터, 배열처럼 접근 필요할 때
- 예 : 게시판 글 목록, 동적 데이터 관리
메모리 사용
- 내부적으로 새 배열 생성 후 기존 데이터 복사 -> 추가 메모리 사용
- 배열 확장 시 순간적으로 2배 크기 배열 필요 -> 메모리 피크 발생 가능

ArrayList<Integer> list = new ArrayList<>();
list.add(10);
list.remove(10);

2. 연결 리스트(Linked List)

각 노드가 값 + 포인터(다음/이전 노드의 주소를 나타냄)
데이터 저장 원리 : 힙에 노드 객체 생성 후 포인터로 연결
데이터 조회 원리 : 헤드부터 순차 탐색 -> O(n)
데이터 삽입/삭제 원리 : 위치 알고 있으면 O(1) (포인터만 변경)
사용 이유 / 사용 시점 :
- 삽입/삭제 빈번, 동적 메모리 필요
- 예 : LRU 캐시, 큐 구현

class Node { int val; Node next; Node(int val){ this.val=val; } }
Node head = new Node(10);
head.next = new Node(20);

3. 스택(Stack)

LIFO(Last In First Out) 구조
데이터 저장/조회 : top에 push/pop
사용 이유 / 사용 시점:
- 순서 뒤집기 , 함수 호출 기록
- 예 : 괄호 검사, DFS

Stack<Character> stack = new Stack<>();
stack.push('(');
stack.pop();

4. 큐(Queue)

FIFO(First In First Out) 구조
데이터 저장/ 조회 : offer(삽입) - tail, poll(값 빼내기) -> head
사용 이유 / 사용 시점 :
- 순서대로 처리 필요
- 예 : BFS, 작업 스케줄링

Queue<Integer> queue = new LinkedList<>();
queue.offer(1);
queue.poll();

5. 해시(Hash Table)

키 - 값 저장
데이터 저장/조회 원리 :
- Key를 해시 함수를 통해 해시값으로 변경
- 해시값을 이용해 버킷 인덱스 계산
- 버킷에 Entry 객체(Key, Value, hash, next) 저장
- 버킷 충돌 발생 시 연결 리스트 또는 트리 구조로 이어서 저장(Chaining) 혹은 다른 빈 버킷을 찾아서 저장(Open Addressing)
사용 이유 / 사용 시점 :
- 검색 최적화, 중복 제거
- 예 : 사용자 ID 매핑, 카운트

HashMap<String, Integer> map = new HashMap<>();
map.put("apple", 3);
map.get("apple");

6. 트리(Tree)

6-1. 이진 탐색 트리(BST, Binary Search Tree)

왼쪽 - 부모 - 오른쪽
데이터 저장/조회 원리 : 루트부터 비교 -> 좌/우 이동
조건 : 0. 정렬 전제 필수
1. 왼쪽 서브트리의 모든 노드 값 < 현재 노드값
2. 오른쪽 서브트리의 모든 노드 값 > 현재 노드값
3. 좌우 서브트리도 각각 BST
사용 이유 / 사용 시점 :
- 정렬된 검색 필요 시
- 예 : 범위 검색

6-2. 힙(Heap)

완전 이진 트리, 최대/최소 규칙
데이터 저장/삭제 원리 :
- 삽입 : 마지막 -> 부모와 비교 -> heapify-up
  - heapify - up 과정(Max Heap기준)
  1. 새 노드를 힙의 마지막 위치에 삽입
  2. 부모와 비교 (새 노드 > 부모 -> 위치 교환)
  3. 루트까지 반복, 조건 만족하면 종료
- 삭제 : 루트 제거 -> 마지막 노드 루트 - heapify-down
  - heapify-down 과정(Max Heap기준)
  1. 루트를 삭제 -> 마지막 노드를 루트 위치로 이동
  2. 자식들과 비교 (자식 중 큰 값과 swap)
  3. 리프까지 반복, 조건 만족하면 종료
원리 :
- 부모와 자식간의 구분
- 자식요소 간 크기 비교는 안됨
사용 이유 / 사용 시점 :
- 최대/최소 값 빠르게 관리
- 예 : 우선순위 큐, 힙 정렬

PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.add(10);
minHeap.poll();

6-3. 트라이(Trie)

문자열 문자 단위로 노드 연결
사용 이유 / 사용 시점 : 자동완성, 문자열 검색

7. 그래프(Graph)

정점(Node)과 간선으로 이루어진 자료 구조
인접 리스트 / 행렬

그래프 탐색 원리 : DFS, BFS

DFS(Depth-First Search)
- 한 방향으로 최대한 깊게 탐색 -> 막다른 길이면 백트래킹
- 스택 기반 또는 재귀 호출 사용
- 사용 시점 : 모든 경로 탐색, 사이클 체크, 연결 요소 찾기
```
boolean[] visited = new boolean[n];
void dfs(int node){
    visited[node] = true;
    for(int next : graph[node]){
        if(!visited[next]) dfs(next);
    }
}
```

BFS(Breadth-First Search)

시작 정점에서 인접한 정점을 먼저 방문 -> 레벨별 탐색
큐 기반
사용 시점 : 최단 경로 탐색, 레벨 탐색, 최소 이동 횟수 계산

Queue<Integer> q = new LinkedList<>();
boolean[] visited = new boolean[n];

q.add(start);
visited[start] = true;

while(!q.isEmpty()){
    int cur = q.poll();
    for(int next : graph[cur]){
        if(!visited[next]){
            visited[next] = true;
            q.add(next);
        }
    }
}

사용 이유 / 사용 시점 : 관계 구조 표현, 최단 경로

Queue<Integer> q = new LinkedList<>();
boolean[] visited = new boolean[n];

알고리즘

1. 정렬(Sorting)

1-1. 선택 정렬(Selection Sort)

동작 원리
1. 배열에서 최소값 선택
2. 현재 위치와 교체
3. 다음 위치 반복
시간 복잡도 : O(n²)
장점 : 구현 단순
단점 : 느림

for(int i=0;i<n-1;i++){
   int min=i;
   for(int j=i+1;j<n;j++)
       if(arr[j]<arr[min]) min=j;
   int tmp=arr[i]; arr[i]=arr[min]; arr[min]=tmp;
}

1-2. 버블 정렬(Bubble Sort)

동작 원리
1. 인접 요소 비교
2. 큰 값 뒤로 이동
3. 반복
시간 복잡도 : O(n²)
장점 : 구현 단순
단점 : 느림

for(int i=0;i<n-1;i++){
    for(int j=0;j<n-1-i;j++){
        if(arr[j] > arr[j+1]){
            int tmp = arr[j];
            arr[j] = arr[j+1];
            arr[j+1] = tmp;
        }
    }
}

1-3. 삽입 정렬(Insertion Sort)

동작 원리 : 이미 정렬된 부분과 비교 -> 적절한 위치 삽입
시간복잡도 : O(n²)
장점 : 거의 정렬된 배열에 빠름
단점 : 큰 배열 느림

for(int i=1;i<n;i++){
    int key = arr[i];
    int j = i - 1;
    while(j >= 0 && arr[j] > key){
        arr[j+1] = arr[j];
        j--;
    }
    arr[j+1] = key;
}

1-4. 퀵 정렬(Quick Sort)

동작 원리
1. pivot 선택
2. pivot 기준 좌/우 분할
3. 재귀 정렬
시간복잡도 : 평균 O(n log n), 최악 O(n²)

void quickSort(int[] arr, int low, int high){
    if(low < high){
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int partition(int[] arr, int low, int high){
    int pivot = arr[high];
    int i = low - 1;
    for(int j=low;j<high;j++){
        if(arr[j] < pivot){
            i++;
            int tmp = arr[i]; arr[i]=arr[j]; arr[j]=tmp;
        }
    }
    int tmp = arr[i+1]; arr[i+1]=arr[high]; arr[high]=tmp;
    return i+1;
}

1-5. 병합 정렬(Merge Sort)

동작 원리
1. 배열 분할
2. 재귀 정렬
3. 병합
시간 복잡도 : O(n log n)
장점 : 안정적

void mergeSort(int[] arr, int l, int r){
    if(l < r){
        int m = l + (r-l)/2;
        mergeSort(arr, l, m);
        mergeSort(arr, m+1, r);
        merge(arr, l, m, r);
    }
}

void merge(int[] arr, int l, int m, int r){
    int n1 = m-l+1, n2 = r-m;
    int[] L = new int[n1]; int[] R = new int[n2];
    for(int i=0;i<n1;i++) L[i] = arr[l+i];
    for(int j=0;j<n2;j++) R[j] = arr[m+1+j];

    int i=0,j=0,k=l;
    while(i<n1 && j<n2){
        if(L[i]<=R[j]) arr[k++] = L[i++];
        else arr[k++] = R[j++];
    }
    while(i<n1) arr[k++] = L[i++];
    while(j<n2) arr[k++] = R[j++];
}

1-6. 힙 정렬(Heap Sort)

동작 원리 : Heap 구성 -> 루트 제거 -> heapify 반복
시간복잡도 : O(n log n)
장점 : in-place, 최대/최소 선택 가능

void heapSort(int[] arr){
    int n = arr.length;
    // 힙 구성
    for(int i=n/2-1;i>=0;i--) heapify(arr,n,i);
    // 루트 제거 + heapify 반복
    for(int i=n-1;i>=0;i--){
        int tmp = arr[0]; arr[0]=arr[i]; arr[i]=tmp;
        heapify(arr,i,0);
    }
}

void heapify(int[] arr, int n, int i){
    int largest = i;
    int l = 2*i + 1;
    int r = 2*i + 2;

    if(l<n && arr[l]>arr[largest]) largest = l;
    if(r<n && arr[r]>arr[largest]) largest = r;

    if(largest != i){
        int tmp = arr[i]; arr[i]=arr[largest]; arr[largest]=tmp;
        heapify(arr,n,largest);
    }
}

2. 탐색(search)

선형 탐색
- 데이터 구조 상관없이 처음부터 끝까지 순차적으로 탐색
- 시간 복잡도 : O(n)
- 자료구조 예시 : 배열(Array), 연결 리스트(LinkedList), 리스트(List) 등
- Linked List와 관련된 이유
  - 연결 리스트는 인덱스로 접근 불가 -> 순차 탐색 필요
```
for(int i=0;i<n;i++){
    if(arr[i] == target) return i;
}
```
이진 탐색
- 정렬된 배열에서 중간 값과 비교 -> 반으로 나눠 탐색
- 시간 복잡도 : O(log n)
- 자료구조 예시
  - 배열(Array) : 인덱스로 중간 값 바로 접근 가능 -> O(log n)
  - 정렬된 이진 탐색 트리(BST) : 트리 구조에서 왼쪽/오른쪽 자식 탐색
```
int low = 0, high = n-1;
while(low <= high){
    int mid = (low+high)/2;
    if(arr[mid] == target) return mid;
    else if(arr[mid] < target) low = mid+1;
    else high = mid-1;
}
```

3. 동적 프로그래밍(DP)

복잡한 문제를 작은 부분 문제로 나누어, 각 부분 문제의 결과를 저장하고 재사용하는 최적의 기법
재귀 + 메모제이션 혹은 테이블(bottom-up) 방식으로 구현
중복 계산 방지, 최적 부분 구조
대표 문제 : LIS, LCS, Kanpsack, 피보나치
사용 이유 / 활용
- 최적화 문제 : 최대/최소 값 계산
- 경로 문제 : 최단 거리, 최대/최대 합 경로
- 조합 문제 : 동전 교환, 배낭 문제
- 문자열 문제 : LCS(Longest Common Subsequence), LIS(Longest Increasing Subsequence)

int[] dp = new int[n];
Arrays.fill(dp,1);
for(int i=1;i<n;i++)
    for(int j=0;j<i;j++)
        if(arr[i]>arr[j]) dp[i]=Math.max(dp[i], dp[j]+1);

4. 그리디(Greedy)ckdla

매 단계 최적 선택
대표 문제 : 거스름돈, 회의실 배정
사용 이유 / 활용
- 최적 선택 기준이 문제 특성상 전체 최적 해로 이어질 때 사용

 int[] coins={500,100,50,10}; int change=760;
 for(int c: coins){ int cnt=change/c; change-=cnt*c; }

5. 백트래킹 / 분기 한정

모든 경우를 탐색하면서 조건에 맞지 않으면 되돌아가면서 탐색하는 기법
후보 선택 후 유효성 확인 -> 조건 맞지 않으면 가지치기
대표 문제 : N-Queen , 순열/조합

void dfs(int row){
    for(int col=0;col<n;col++){
        if(isValid(row,col)){
            board[row][col]=1;
            dfs(row+1);
            board[row][col]=0;
        }
    }
}